package dp_algorithm.nowcoder.medium;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @author bruin_du
 * @description 公共子串长度的计算
 * https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b?
 * tpId=37&&tqId=21298&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
 * @date 2022/5/17 9:14
 **/
public class CountCommonStringLength {
    public static void main(String[] args) {
        //循环遍历的方法,三层循环
        //还可以用动态规划的方法
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str1 = in.next();
            String str2 = in.next();
            String longStr = str1.length() > str2.length() ? str1 : str2;
            String shortStr = str1.length() > str2.length() ? str2 : str1;
            int longLength = longStr.length();
            int shortLength = shortStr.length();
            Set<Character> set = new HashSet<>();
            int retLength = 0;
            //将短字符串存入set去重,为了判断在长字符串的字符是否在短字符串存在
            for (int i = 0; i < shortLength; i++) {
                set.add(shortStr.charAt(i));
            }
            //从长字符串的第一个字符开始往后找最长子串
            for (int i = 0; i < longLength; i++) {
                char chL = longStr.charAt(i);
                //在短字符串存在该字符
                if (set.contains(chL)) {
                    //每次都从短字符串开始位置往后查找
                    int indexOfShortStr = 0;
                    int pIndexOfS;
                    //逐个找到与长字符串的字符相同处往后计算相同字符串的长度
                    while ((pIndexOfS = shortStr.indexOf(chL, indexOfShortStr)) != -1) {
                        StringBuilder sb = new StringBuilder();
                        int pIndexOfL = i;
                        //都往后加一记录公共字符串
                        while (pIndexOfS < shortLength && pIndexOfL < longLength &&
                                shortStr.charAt(pIndexOfS) == longStr.charAt(pIndexOfL)) {
                            sb.append(shortStr.charAt(pIndexOfS));
                            pIndexOfL++;
                            pIndexOfS++;
                        }
                        if (sb.length() > retLength)
                            retLength = sb.length();
                        indexOfShortStr++;
                    }
                }
            }
            System.out.println(retLength);
        }
    }
}
